#include<iostream>
using namespace std;
#define N 100 
int parent[N];
// 2.1 MakeSet（x） 建立一个新的集合

// 建立一个新的集合，其唯一成员（因为是其代表）就是x。因为集合是不相交的，故要求x没有在其它集合中出现过。

// 2.2 Find（x） 包含x集合的代表

// 返回一个指针，指向包含x的（唯一）集合的代表。

// 2.3 Union（x，y） 合并两个不相交集合

// 将包含x和y的动态集合合并成为一个新的集合。所得集合的代表可以是两个集合的任何成员。但在很多情况下，我们一般选择两个集合之前代表中的一个作为新的代表。

void MakeSet(int x)
{
    parent[x] = x;
}

int Find(int x)
{
    // while (x != parent[x])
    // {
    //     x = parent[x];
    // }
    // return x;
    //迭代版
    if( x != parent[x])
        parent[x] = Find(parent[x]); //路径压缩
    return parent[x] ;
}

void Union(int x ,int y)
{
    x = Find(x);
    y = Find(y);
    parent[y] = x;
}

int main()
{
    MakeSet(1);
    MakeSet(2);
    MakeSet(3);
    MakeSet(4);
    MakeSet(5);
    Union(5,4);
    Union(4,3);
    cout<<Find(3);
    return 0;

}